package String;
/**
 *
 * 描述
 * 给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 ,
 * 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。
 *
 * 数据范围： 0≤n≤5000， 0≤len(strs)≤5000
 * i

 * 进阶：空间复杂度 O(n)，时间复杂度 O(n)
 * 示例1
 * 输入：
 * ["abca","abc","abca","abc","abcc"]
 * 返回值：
 * "abc"
 * 示例2
 * 输入：
 * ["abc"]
 * 返回值：
 * "abc"
 *
 * */


class BM84 {
    /**
     *
     * @param strs string字符串一维数组
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        // write code here
        int len = strs.length;
        //特例判断
        if(len==0){
            return "";
        }
        if(len==1){
            return strs[0];
        }
//         return verticalTraversal(strs);
        return lateralTraversal(strs);

    }

    //纵向扫描，即每次从第一个字符串中取一个字符，遍历其它的对应位置是否相同
    private String verticalTraversal(String[] strs){
        int rows = strs.length;  //总共多少个字符串
        int cols = strs[0].length();  //第一个字符串的长度
        for(int i=0;i<cols;i++){
            char c = strs[0].charAt(i);  //取当前字符
            for(int j=1;j<rows;j++){  //遍历剩下的每一个字符串
                if(strs[j].length()==i || strs[j].charAt(i)!=c){
                    return strs[0].substring(0,i);  //当前已经不满足了
                }
            }
        }
        return strs[0];
    }
    //横向遍历，得出i,i+1两个字符串的公共前缀然后再拿公共前缀和i+2的字符串取公共前缀
    private String lateralTraversal(String[] strs){
        String prefix = strs[0]; //取第一个当公共前缀
        for(int i=1;i<strs.length;i++){
            prefix = getConmmonPrefix(prefix,strs[i]);
            if("".equals(prefix)){
                return "";
            }
        }
        return prefix;

    }

    //返回两子串公共前缀函数
    private String getConmmonPrefix(String s1, String s2){
        int len= Math.min(s1.length(),s2.length());
        int flag=0;
        while(flag<len && s1.charAt(flag)==s2.charAt(flag)){
            flag++;
        }
        return s1.substring(0,flag);
    }
}
